package cn.edu.xjtu.work.maxSubArrayDeleteOne;

/**
 * @author Hydrion-QLz
 * @date 2022-09-17 21:17
 * @description 最大子数组和
 * 给定一个数组，可以任意删除一个元素，返回其最大的连续子数组的和
 */
public class Solution {
    public static void main(String[] args) {
        int[][] arr = {{5, 7, -3, 2}, {0, -1, -2, 3}, {1, 2, 5, -2, 3, -1, 6}, {-2, -2, -2, -2}};
        for (int[] val : arr) {
            System.out.println(maxSubArray(val));
        }
    }

    private static int maxSubArray(int[] arr) {
        int[] deleteOne = new int[arr.length];
        int[] notDelete = new int[arr.length];
        deleteOne[0] = arr[0];
        notDelete[0] = arr[0];
        int maxVal = arr[0];
        for (int i = 1; i < arr.length; i++) {
            deleteOne[i] = Math.max(deleteOne[i - 1] + arr[i], Math.max(arr[i], notDelete[i - 1]));
            notDelete[i] = Math.max(notDelete[i - 1] + arr[i], arr[i]);
            maxVal = Math.max(maxVal, Math.max(notDelete[i], deleteOne[i]));
        }
        return maxVal;
    }

}
